#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_
#include<stddef.h>
#include<limits.h>
#include<iostream>
using ElementType = void*;

class DynamicArray
{
public:
    DynamicArray(size_t capacity = 15);
    DynamicArray(const DynamicArray& a);
    DynamicArray& operator=(const DynamicArray& a);
    ~DynamicArray();

    size_t Size();
    //扩容接口
    void ReSize(size_t capacity);

    //尾部插入
    void InsertTail(const ElementType& element);
    //头部插入
    void InsertHead(const ElementType& element);
    //中间插入
    void InsertByIndex(int index, const ElementType& element);

    //按位置删除
    void RemoveByIndex(int index);
    //按值删除
    void RemoveByElement(const ElementType& element);

    //按位置查找
    ElementType* FindByIndex(int index);
    //按值查找
    DynamicArray FindByElement(const ElementType& element);
    ElementType FindElement(DynamicArray* a,std::string elem1,int elem2,bool(*EqualPtr)(ElementType,std::string,int));

    //按位置修改
    void UpdateByIndex(int index, const ElementType& element);
    //按值修改
    void UpdateByElement(const ElementType& oldValue, const ElementType& newValue);

    //排序
    void Sort(bool (*SortPtr)(ElementType, ElementType)); 
    //去重算法
    void Duplicate(bool (*EqualPtr)(ElementType, ElementType));
    //归并算法：合并两个数组已经有序的数列
    DynamicArray Merge(const DynamicArray& a,bool(*EqualPtr)(ElementType, ElementType));
    //找交集
    DynamicArray FindInterSection(const DynamicArray& a,bool (*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType));
    //找并集
    DynamicArray FindUnionSection(const DynamicArray& a,bool(*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType));
    //找补集
    DynamicArray FindDifferentSection(const DynamicArray& a,bool(*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType));

    //判断两个数列是否相等
    bool operator==(const DynamicArray& a);

    //二分查找
    size_t BinarySearch(const ElementType& element);

    //查找一个数列是不是子数列
    bool IsChild(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType));
    //查找连续子数列
    bool IsContinueChild(const DynamicArray& a,bool(*EqualPtr)(ElementType, ElementType));
    //获取子序列
    DynamicArray subsequence(int index,size_t size);
    
    //显示
    void show(void(*PrintPtr)(ElementType));

    void SetFreePtr();

private:
    //快速排序
    void FastSort(size_t start, size_t end,size_t deepth,size_t MaxDepth,bool (*SortPtr)(ElementType, ElementType));
    //插入排序
    void InsertSort(size_t start, size_t end, bool (*SortPtr)(ElementType, ElementType));
    //分组函数
    size_t Partition(size_t start, size_t end,bool (*SortPtr)(ElementType, ElementType));

    ElementType* array;
    size_t capacity;
    size_t size;
    void(*FreePtr)(ElementType);//数组元素释放的函数指针
    void(*PrintPtr)(ElementType);//打印元素的函数指针
    bool(*SortPtr)(ElementType,ElementType);//排序指针
    bool(*EqualPtr)(ElementType,ElementType);//比较指针
    bool(*FindPtr)(ElementType,ElementType);//比较指针
};
#endif